from utils.qs import QS
from utils.log import Log
from utils.generator import Generator


class RecursiveStack(Log):
    def __init__(self, s):
        super(RecursiveStack, self).__init__()
        self.s = s
        if isinstance(s, list):
            self.s = QS(is_queue=False, val=s)

    def bottom_out(self):
        ans = self.s.pop()
        if self.s.is_empty():
            return ans
        else:
            last = self.bottom_out()
            self.s.push(ans)
            return last

    def reverse(self):
        # https://www.bilibili.com/video/BV19m4y1n7mo/?spm_id_from=333.999.0.0&vd_source=ad559e41b561d48861f70d0187e51e02
        # 01:06:46
        if self.s.is_empty():
            return
        num = self.bottom_out()
        self.reverse()
        self.s.push(num)

    def times(self, deep, max_value):
        if deep == 0:
            return 0
        num = self.s.pop()
        rest_times = self.times(deep - 1, max_value)
        times = rest_times + (1 if num == max_value else 0)
        self.s.push(num)
        return times

    def down(self, deep, max_val, times):
        if deep == 0:
            for _ in range(times):
                self.s.push(max_val)
        else:
            num = self.s.pop()
            self.down(deep - 1, max_val, times)
            if num != max_val:
                self.s.push(num)

    def sort(self):
        deep = len(self.s)
        while deep > 0:
            # 不建议用以下两个表达式,只是针对stack的操作
            max_val = max(self.s.c[len(self.s) - deep:])
            # times = self.times(deep, max_val)
            times = self.s.c[len(self.s) - deep:].count(max_val)
            self.down(deep, max_val, times)
            deep -= times


if __name__ == '__main__':
    s = QS(False)
    s.push('a')
    s.push('b')
    s.push('c')
    s.push('d')
    print(s.c)
    rs = RecursiveStack(s)
    rs.reverse()
    print(s.c)

    vals = Generator().do()
    rs1 = RecursiveStack(vals)
    print(vals)
    rs1.sort()
    print(vals)
